1. Technical Field
The present invention relates primarily to the control of data in a network.
As will be explained in detail later, preferred embodiments of the invention are concerned with characterising the path traversed by data through a network where each node characterises its local part of the path and then all these local characterisations are accumulated in the data as it passes. For instance the time to live (TTL) field and the explicit congestion notification (ECN) field in the Internet Protocol (IP) header work this way.
2. Related Art
Currently, all known forms of path characterisation initialise the field intended to collect the path characterisation to a set, standardised value. Often, the value accumulated at the destination is fed back to the source. In a co-pending application having publication number WO2005/096566, the subject matter of which is incorporated herein by reference, we described the advantages of ensuring that the initial value of one of these characterisation fields is arranged so that, by the time it has accumulated path information, it tends to arrive at the destination carrying a commonly standardised value. We will refer to the concept set out in this earlier application as “Re-feedback”, this term being indicative of the idea of “Receiver-Normalised” feedback (as opposed to “classic” or “traditional” feedback, which in this context may be thought of as “Source-Normalised”). Feedback from the destination to the source may then be used to continuously correct any error in the destination value when future data is sent. A principal advantage is that data effectively carries with it a prediction of its own downstream path for use by in-line equipment along the transmission path.
Although re-feedback brings many advantages, it will be all the more useful if a way can be found to introduce it into current networks by incremental deployment. Specifically, traffic carrying path characterisation should identify itself as based on re-feedback, but it should not be necessary for all relays on a path to be upgraded before re-feedback can be introduced. Then pairs of hosts can arrange traffic between them to carry path characterisation based on re-feedback if they have both been upgraded. But where one or both have not been upgraded, classic feedback can continue to be used.
As will be explained in detail later, preferred embodiments of the invention are concerned with ways to introduce re-feedback of explicit congestion notification into the two bits of the Internet protocol already used for congestion notification without necessarily altering the Internet protocol format and without contravening the current ECN standard (IETF RFC3168)—only altering the semantics of how the fields are understood. For brevity, we will call this concept “re-ECN”.
Superimposed Coding of Information in Repeated Data Fields
Current communications protocols are developed to carry data efficiently over a network according to a given set of requirements. They all use similar structures composed of (some of) the payload data augmented by a protocol header so that the proper service can be provided. Given the global scope of today's communications, standard bodies define exactly what information is put in the headers. Given that header information increases the communication overhead, header fields are usually constrained by very strict size limits. Also, it is easier to design transmission hardware if fields are of known size in known positions within a packet or frame. Therefore it is desirable to be able to communicate signals (that is numbers that change over time) in protocol fields that are smaller than the accuracy required of the signal.
Further, when a protocol design becomes a standard there is very little flexibility to change the length, the nature, the meaning or the use of the fields that were agreed in the first place. However as more services are proposed, as more threats appear, and for other reasons, there is a need to adjust and change the information carried in packet headers. So the meaning of fields that were designed to be large enough often needs to be overloaded with new meaning(s) without increasing its size.
A known technique is to spread information over repeated occurrences of the same field in a protocol. So that, over time, more bits of accuracy can be communicated than the restricted field size seems to allow.
Naïvely, different parts of the same bit representation of a number can be communicated in different packets. But for the reader to interpret the meaning, it must share some context (“state”) with the writer. For instance, imagine communicating a 16-bit number in an 8-bit field. We might use the convention that the meaning of the field depends on whether another associated sequence number is odd or even (odd meaning lower significant bits, even meaning higher). Then the reader could put together the pairs of fields with sequence numbers 1,2; 3,4; . . . 19,20 to get the full field.
However, this naïve approach is not useful where the protocol is intended to communicate moving values and be stateless. For instance, unlike IP hosts, IP routers are designed on the principle that state is never created to remember any values in a packet from one packet to the next (routers may create their own aggregate state variables with values derived from all packets, e.g. a counter for accounting). So, even if a router were merely trying to find the moving average value of a field across many packets (for whatever reason), averaging all the odds and averaging all the evens separately wouldn't work.
For example, in a similar vein to the above naïve scenario, imagine finding the moving average over a moving window of values out of the sequence {2.1, 1.8, 2.1, 1.7} by averaging {2, 1, 2, 1} and {0.1, 0.8, 0.1, 0.7} separately. Even if these packets identify themselves as odd or even, they also need to be averaged in order. Imagine the first two values of the higher order sequence arrive out of order. The result would be the average of the sequence {2.8, 2.1, 1.1, 1.7}. This is fine if all the numbers are averaged, but not if the average is moving. For instance the average of the last three numbers is different in the two cases. This naïve approach leads to a systematic bias of error when the signal transitions between one high order number and the next.
In 1987, to address the need for stateless coding of a moving number across repeated instances of a protocol field, DEC developed the approach [Jain87] where the number is repeatedly rounded up or down, with the proportion of roundings down against up continuously increasing the accuracy, but also moving as the number to be communicated moves. So for instance 0.4 could be represented by the sequence of single bits {1,0,1,0,1} or {1,0,1,0,1,1,0,1,0,1, . . . }. Then, if the number changed to 0.2, the sequence would reflect the change: {1,0,1,0,1,1,0,1,0,1, . . . 1,1,0,1,1,}. Although there are random fluctuations in accuracy, there is no systematic bias of error up or down with this technique. Unlike the naïve approach, no packet carries information that is meaningless unless combined with information from another packet to reconstruct the meaning.
As will be explained in detail later, preferred embodiments of the present invention build on this tradition.
Another prior mechanism of relevance is the PURPLE mechanism proposed by Mannal et al [Mannal2003] to which US patent application US 2004/190449 relates, which monitors the occurrence rate of the CWR flag in TCP headers to estimate the end-to-end congestion level a round-trip earlier. With the standard ECN specifications, for each congestion mark (CE, indicating “Congestion Experienced”, in the IP header), echoes are sent in all acknowledgments (ECE, the “ECN-Echo” flag, in the TCP header) until the destination receives confirmation that the source has acted upon the congestion signal (CWR, the “Congestion Window Reduced” flag, in the TCP header). This means that CWR flags are going to travel across every node on the path, at the same rate as CE marks reach the destination, with a delay of one round-trip. Mannal et al further suggests to keep in memory the rate of CE marks arriving at any given node for a round-trip. From the end-to-end congestion signal the node receives a round-trip later, the node can extract the downstream congestion level on the path a round-trip earlier. Mannal et al proposes using the value, in combination with the current upstream congestion signal, to control the convergence of the adaptive queue management mechanism on the congested router.
This approach gives very accurate information in the case of a non-encrypted TCP flows. However, the necessary information may not be available in other common cases, such as, for example:                if IPSec is used, the TCP header is encrypted, and it becomes impossible to monitor the occurrence rate of CWR flags;        if IPSec is not used but the transport protocol is UDP (as would be the case for RTP streaming traffic), CWR flags cannot be monitored either.        
International application WO2004/049649 (King's College London) relates to differentiated marking on routers. It refers to the respective treatment of two groups of packets, referred to as a “first proportion” and a “second proportion”. Packets that have spent less time on the network are regarded as being in the first group, and are more likely to be marked than packets that have spent more time on the network, which are regarded as being in the second group. The respective treatments of individual packets deemed to be in the first and second groups thus depend on how long the packets have spent on the network.